#include<bits/stdc++.h>
using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};


// /**
//  * 2021.9.27
//  * Solution1:
//  * 使用哈希表记录原节点对应的新节点以方便后面为 random 指针赋值。
//  */
// class Solution {
// public:
//     unordered_map<Node*, Node*> mp;
//     Node* copyRandomList(Node* head) {
//         if(!head)return nullptr;
//         Node* ans = new Node(head->val), *mov = ans, *origin_mov = head->next;
//         mp[head] = ans;
//         while(origin_mov){
//             mov->next = new Node(origin_mov->val);
//             mov = mov->next;
//             mp[origin_mov] = mov;
//             origin_mov = origin_mov->next;
//         }      
//         mov = ans;
//         origin_mov = head;
//         while(origin_mov){
//             mov->random = mp[origin_mov->random];
//             origin_mov = origin_mov->next;
//             mov = mov->next;
//         }
//         return ans;
//     }
// };



class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)return nullptr;
        Node *ans, *mov, *origin_mov = head;
        
        //生成新节点
        while(origin_mov){
            mov = new Node(origin_mov->val);
            mov->next = origin_mov->next;
            origin_mov->next = mov;
            origin_mov->next->random = origin_mov->random;
            origin_mov = mov->next;
        }

        //修改新节点的 random 指针
        mov = head->next;
        while(mov){
            if(mov->random)mov->random = mov->random->next;
            if(mov->next)mov = mov->next->next;
            else break;
        }

        //将新节点与原节点分离
        ans = head->next;
        mov = head;
        Node* q = mov->next;
        while(true){
            mov->next = q->next;
            mov = q->next;
            if(!mov)break;
            if(mov)q->next = mov->next;
            if(mov)q = mov->next;
        }
        return ans;
    }
};


/**
 * 2021.9.28
 * 两种方法，一种是用哈希表记录原节点对应的新节点，
 * 另一种是在原链表每个节点插入一个复制节点，这样找每个节点的
 * random 位置就是原节点 random 指向的节点的下一个节点。
 */